// 字典
var JsFenciDict = [
  "家乡",
  "松花",
  "松花江",
  "那里",
  "四季",
  "四季迷人",
  "迷人",
  "花香",
  "hello",
  "kitty",
  "fine"
];

// 停止词
var JsFenciStop = {
  '第二': 1,
  '一番': 1,
  '一直': 1,
  '一个': 1,
  '一些': 1,
  '许多': 1,
  '有的是': 1,
  '也就是说': 1,
  '末##末': 1,
  '啊': 1,
  '阿': 1,
  '哎': 1,
  '哎呀': 1,
  '哎哟': 1,
  '唉': 1,
  '俺': 1,
  '俺们': 1,
  '按': 1,
  '按照': 1,
  '吧': 1,
  '吧哒': 1,
  '把': 1,
  '罢了': 1,
  '被': 1,
  '本': 1,
  '本着': 1,
  '比': 1,
  '比方': 1,
  '比如': 1,
  '鄙人': 1,
  '彼': 1,
  '彼此': 1,
  '边': 1,
  '别': 1,
  '别的': 1,
  '别说': 1,
  '并': 1,
  '并且': 1,
  '不比': 1,
  '不成': 1,
  '不单': 1,
  '不但': 1,
  '不独': 1,
  '不管': 1,
  '不光': 1,
  '不过': 1,
  '不仅': 1,
  '不拘': 1,
  '不论': 1,
  '不怕': 1,
  '不然': 1,
  '不如': 1,
  '不特': 1,
  '不惟': 1,
  '不问': 1,
  '不只': 1,
  '朝': 1,
  '朝着': 1,
  '趁': 1,
  '趁着': 1,
  '乘': 1,
  '冲': 1,
  '除': 1,
  '除此之外': 1,
  '除非': 1,
  '除了': 1,
  '此': 1,
  '此间': 1,
  '此外': 1,
  '从': 1,
  '从而': 1,
  '打': 1,
  '待': 1,
  '但': 1,
  '但是': 1,
  '当': 1,
  '当着': 1,
  '到': 1,
  '得': 1,
  '的': 1,
  '的话': 1,
  '等': 1,
  '等等': 1,
  '第': 1,
  '叮咚': 1,
  '对': 1,
  '对于': 1,
  '多': 1,
  '多少': 1,
  '而': 1,
  '而况': 1,
  '而且': 1,
  '而是': 1,
  '而外': 1,
  '而言': 1,
  '而已': 1,
  '尔后': 1,
  '反过来': 1,
  '反过来说': 1,
  '反之': 1,
  '非但': 1,
  '非徒': 1,
  '否则': 1,
  '嘎': 1,
  '嘎登': 1,
  '该': 1,
  '赶': 1,
  '个': 1,
  '各': 1,
  '各个': 1,
  '各位': 1,
  '各种': 1,
  '各自': 1,
  '给': 1,
  '根据': 1,
  '跟': 1,
  '故': 1,
  '故此': 1,
  '固然': 1,
  '关于': 1,
  '管': 1,
  '归': 1,
  '果然': 1,
  '果真': 1,
  '过': 1,
  '哈': 1,
  '哈哈': 1,
  '呵': 1,
  '和': 1,
  '何': 1,
  '何处': 1,
  '何况': 1,
  '何时': 1,
  '嘿': 1,
  '哼': 1,
  '哼唷': 1,
  '呼哧': 1,
  '乎': 1,
  '哗': 1,
  '还是': 1,
  '还有': 1,
  '换句话说': 1,
  '换言之': 1,
  '或': 1,
  '或是': 1,
  '或者': 1,
  '极了': 1,
  '及': 1,
  '及其': 1,
  '及至': 1,
  '即': 1,
  '即便': 1,
  '即或': 1,
  '即令': 1,
  '即若': 1,
  '即使': 1,
  '几': 1,
  '几时': 1,
  '己': 1,
  '既': 1,
  '既然': 1,
  '既是': 1,
  '继而': 1,
  '加之': 1,
  '假如': 1,
  '假若': 1,
  '假使': 1,
  '鉴于': 1,
  '将': 1,
  '较': 1,
  '较之': 1,
  '叫': 1,
  '接着': 1,
  '结果': 1,
  '借': 1,
  '紧接着': 1,
  '进而': 1,
  '尽': 1,
  '尽管': 1,
  '经': 1,
  '经过': 1,
  '就': 1,
  '就是': 1,
  '就是说': 1,
  '据': 1,
  '具体地说': 1,
  '具体说来': 1,
  '开始': 1,
  '开外': 1,
  '咳': 1,
  '可见': 1,
  '可是': 1,
  '可以': 1,
  '况且': 1,
  '啦': 1,
  '来着': 1,
  '离': 1,
  '例如': 1,
  '哩': 1,
  '连': 1,
  '连同': 1,
  '两者': 1,
  '了': 1,
  '临': 1,
  '另': 1,
  '另外': 1,
  '另一方面': 1,
  '论': 1,
  '嘛': 1,
  '吗': 1,
  '慢说': 1,
  '漫说': 1,
  '冒': 1,
  '么': 1,
  '每': 1,
  '每当': 1,
  '们': 1,
  '莫若': 1,
  '某': 1,
  '某个': 1,
  '某些': 1,
  '拿': 1,
  '哪': 1,
  '哪边': 1,
  '哪儿': 1,
  '哪个': 1,
  '哪里': 1,
  '哪年': 1,
  '哪怕': 1,
  '哪天': 1,
  '哪些': 1,
  '哪样': 1,
  '那': 1,
  '那边': 1,
  '那儿': 1,
  '那个': 1,
  '那会儿': 1,
  '那里': 1,
  '那么': 1,
  '那么些': 1,
  '那么样': 1,
  '那时': 1,
  '那些': 1,
  '那样': 1,
  '乃': 1,
  '乃至': 1,
  '呢': 1,
  '能': 1,
  '你': 1,
  '你们': 1,
  '您': 1,
  '宁': 1,
  '宁可': 1,
  '宁肯': 1,
  '宁愿': 1,
  '哦': 1,
  '呕': 1,
  '啪达': 1,
  '旁人': 1,
  '呸': 1,
  '凭': 1,
  '凭借': 1,
  '其': 1,
  '其次': 1,
  '其二': 1,
  '其他': 1,
  '其它': 1,
  '其一': 1,
  '其余': 1,
  '其中': 1,
  '起': 1,
  '起见': 1,
  '起见': 1,
  '岂但': 1,
  '恰恰相反': 1,
  '前后': 1,
  '前者': 1,
  '且': 1,
  '然而': 1,
  '然后': 1,
  '然则': 1,
  '让': 1,
  '人家': 1,
  '任': 1,
  '任何': 1,
  '任凭': 1,
  '如': 1,
  '如此': 1,
  '如果': 1,
  '如何': 1,
  '如其': 1,
  '如若': 1,
  '如上所述': 1,
  '若': 1,
  '若非': 1,
  '若是': 1,
  '啥': 1,
  '上下': 1,
  '尚且': 1,
  '设若': 1,
  '设使': 1,
  '甚而': 1,
  '甚么': 1,
  '甚至': 1,
  '省得': 1,
  '时候': 1,
  '什么': 1,
  '什么样': 1,
  '使得': 1,
  '是': 1,
  '是的': 1,
  '首先': 1,
  '谁': 1,
  '谁知': 1,
  '顺': 1,
  '顺着': 1,
  '似的': 1,
  '虽': 1,
  '虽然': 1,
  '虽说': 1,
  '虽则': 1,
  '随': 1,
  '随着': 1,
  '所': 1,
  '所以': 1,
  '他': 1,
  '他们': 1,
  '他人': 1,
  '它': 1,
  '它们': 1,
  '她': 1,
  '她们': 1,
  '倘': 1,
  '倘或': 1,
  '倘然': 1,
  '倘若': 1,
  '倘使': 1,
  '腾': 1,
  '替': 1,
  '通过': 1,
  '同': 1,
  '同时': 1,
  '哇': 1,
  '万一': 1,
  '往': 1,
  '望': 1,
  '为': 1,
  '为何': 1,
  '为了': 1,
  '为什么': 1,
  '为着': 1,
  '喂': 1,
  '嗡嗡': 1,
  '我': 1,
  '我们': 1,
  '呜': 1,
  '呜呼': 1,
  '乌乎': 1,
  '无论': 1,
  '无宁': 1,
  '毋宁': 1,
  '嘻': 1,
  '吓': 1,
  '相对而言': 1,
  '像': 1,
  '向': 1,
  '向着': 1,
  '嘘': 1,
  '呀': 1,
  '焉': 1,
  '沿': 1,
  '沿着': 1,
  '要': 1,
  '要不': 1,
  '要不然': 1,
  '要不是': 1,
  '要么': 1,
  '要是': 1,
  '也': 1,
  '也罢': 1,
  '也好': 1,
  '一': 1,
  '一般': 1,
  '一旦': 1,
  '一方面': 1,
  '一来': 1,
  '一切': 1,
  '一样': 1,
  '一则': 1,
  '依': 1,
  '依照': 1,
  '矣': 1,
  '以': 1,
  '以便': 1,
  '以及': 1,
  '以免': 1,
  '以至': 1,
  '以至于': 1,
  '以致': 1,
  '抑或': 1,
  '因': 1,
  '因此': 1,
  '因而': 1,
  '因为': 1,
  '哟': 1,
  '用': 1,
  '由': 1,
  '由此可见': 1,
  '由于': 1,
  '有': 1,
  '有的': 1,
  '有关': 1,
  '有些': 1,
  '又': 1,
  '于': 1,
  '于是': 1,
  '于是乎': 1,
  '与': 1,
  '与此同时': 1,
  '与否': 1,
  '与其': 1,
  '越是': 1,
  '云云': 1,
  '哉': 1,
  '再说': 1,
  '再者': 1,
  '在下': 1,
  '咱': 1,
  '咱们': 1,
  '则': 1,
  '怎': 1,
  '怎么': 1,
  '怎么办': 1,
  '怎么样': 1,
  '怎样': 1,
  '咋': 1,
  '照': 1,
  '照着': 1,
  '者': 1,
  '这': 1,
  '这边': 1,
  '这儿': 1,
  '这个': 1,
  '这会儿': 1,
  '这就是说': 1,
  '这里': 1,
  '这么': 1,
  '这么点儿': 1,
  '这么些': 1,
  '这么样': 1,
  '这时': 1,
  '这些': 1,
  '这样': 1,
  '正如': 1,
  '吱': 1,
  '之': 1,
  '之类': 1,
  '之所以': 1,
  '之一': 1,
  '只是': 1,
  '只限': 1,
  '只要': 1,
  '只有': 1,
  '至': 1,
  '至于': 1,
  '诸位': 1,
  '着': 1,
  '着呢': 1,
  '自从': 1,
  '自个儿': 1,
  '自各儿': 1,
  '自己': 1,
  '自家': 1,
  '自身': 1,
  '综上所述': 1,
  '总的来看': 1,
  '总的来说': 1,
  '总的说来': 1,
  '总而言之': 1,
  '总之': 1,
  '纵': 1,
  '纵令': 1,
  '纵然': 1,
  '纵使': 1,
  '遵照': 1,
  '作为': 1,
  '兮': 1,
  '呃': 1,
  '呗': 1,
  '咚': 1,
  '咦': 1,
  '喏': 1,
  '啐': 1,
  '喔唷': 1,
  '嗬': 1,
  '嗯': 1,
  '嗳': 1,
};


// JsFenci树
function JsFenci() {
  this.root = new JsFenciNode(null);
}
JsFenci.prototype = {
  /**
  * 将Unicode转成UTF8的三字节
  */
  toBytes: function (word) {
    var result = [];
    for (var i = 0; i < word.length; i++) {
      var code = word.charCodeAt(i);
      // 单字节
      if (code < 0x80) {
        result.push(code);
      } else {
        // 三字节
        result = result.concat(this.toUTF8(code));
      }
    }

    return result;
  },
  toUTF8: function (c) {
    // 1110xxxx 10xxxxxx 10xxxxxx
    // 1110xxxx
    var byte1 = 0xE0 | ((c >> 12) & 0x0F);
    // 10xxxxxx
    var byte2 = 0x80 | ((c >> 6) & 0x3F);
    // 10xxxxxx
    var byte3 = 0x80 | (c & 0x3F);

    return [byte1, byte2, byte3];
  },
  toUTF16: function (b1, b2, b3) {
    // 1110xxxx 10xxxxxx 10xxxxxx
    var byte1 = (b1 << 4) | ((b2 >> 2) & 0x0F);
    var byte2 = ((b2 & 0x03) << 6) | (b3 & 0x3F);
    var utf16 = ((byte1 & 0x00FF) << 8) | byte2

    return utf16;
  },
  /**
  * 添加每个词到JsFenci树
  */
  add: function (word) {
    var node = this.root, bytes = this.toBytes(word), len = bytes.length;
    for (var i = 0; i < len; i++) {
      var c = bytes[i];
      // 如果不存在则添加，否则不需要再保存了，因为共用前缀
      if (!(c in node.childs)) {
        node.childs[c] = new JsFenciNode(c);
      }
      node = node.childs[c];
    }
    node.asWord(); // 成词边界
  },
  /**
  * 按字节在JsFenci树中搜索
  */
  search: function (bytes) {
    var node = this.root, len = bytes.length, result = [];
    var word = [], j = 0;
    for (var i = 0; i < len; i++) {
      var c = bytes[i], childs = node.childs;
      if (!(c in childs)) {
        return result;
      }

      if (c < 0x80) {
        word.push(String.fromCharCode(c));
      } else {
        j++;
        if (j % 3 == 0) {
          var b1 = bytes[i - 2];
          var b2 = bytes[i - 1];
          var b3 = c;
          word.push(String.fromCharCode(this.toUTF16(b1, b2, b3)));
        }
      }
      // 如果是停止词，则退出
      if (word.join('') in JsFenciStop) {
        return result;
      }

      // 成词
      var cnode = childs[c];
      if (cnode.isWord()) {
        cnode.addCount(); // 用于计数判断
        result.push(word.join(''));
      }

      node = cnode;
    }

    return result;
  },
  /**
  * 分词
  */
  splitWords: function (words) {
    // 转换成单字节进行搜索
    var bytes = this.toBytes(words);
    var start = 0, end = bytes.length - 1, result = [];

    while (start != end) {
      var word = [];
      for (var i = start; i <= end; i++) {
        var b = bytes[i]; // 逐个取出字节
        word.push(b);

        var finds = this.search(word);
        if (finds !== false && finds.length > 0) {
          // 如果在字典中，则添加到分词结果集
          result = result.concat(finds);
        }
      }

      start++;
    }

    return result;
  },
  /**
  * 词始化整棵JsFenci树
  */
  init: function (userDict) {
    var dict = userDict || JsFenciDict;
    for (var i = 0; i < dict.length; i++) {
      this.add(dict[i]);
    }
  }
};

// 节点
function JsFenciNode(_byte) {
  this.childs = {}; // 子节点集合
  this._byte = _byte || null; // 此节点上存储的字节
  this._isWord = false; // 边界保存，表示是否可以组成一个词
  this._count = 0;
}
JsFenciNode.prototype = {
  isWord: function () {
    return (this._isWord && (this._count == 0));
  },
  asWord: function () {
    this._isWord = true;
  },
  addCount: function () {
    this._count++;
  },
  getCount: function () {
    return this._count;
  }
};